/*
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串 s ，判断字符串是否有效。

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = "()"
输出：true

示例2：
输入：s = "()[]{}"
输出：true

示例3：
输入：s = "(]"
输出：false

链接：https://leetcode.cn/problems/valid-parentheses
 */
package LC0020;

import java.util.Stack;

public class Solution1 {

    // 栈
    public boolean isValid(String s) {
        // 总是要考虑输入为空的情况
        if(s.isEmpty())
            return true;

        Stack<Character> stack=new Stack<Character>(); // TODO stack可以用范型?

        for(char c:s.toCharArray()){
            // 如果是左括号，栈就push右括号
            if(c=='(')
                stack.push(')');
            else if(c=='{')
                stack.push('}');
            else if(c=='[')
                stack.push(']');
            //  stack.empty() 即第一个字符是 右括号，肯定错误
            //  如果是右括号，出栈，c != stack.pop() 即左右字符不匹配
            else if(stack.empty() || c != stack.pop())
                return false;
        }
        // 如果左右匹配，全部出栈，栈空；
        if(stack.empty())
            return true;

        // 如果最后一个字符是左括号
        return false;   // TODO 上面不是已经把所有情况都分析了吗？
    }
}
